The present invention relates to decompression and, more particularly, to decompression of video information.
Because video information requires a large amount of storage space, video information is generally compressed. Accordingly, to display compressed video information which is stored, for example on a compact disk read only memory (CD ROM), the compressed video information must be decompressed to provide decompressed video information. The decompressed video information is then provided in a bit stream to a display. The bit stream of video information is generally stored in a plurality of memory storage locations corresponding to pixel locations on a display, the stored video information is generally referred to as a bit map. The video information required to present a single screen of information on a display is called a frame. A goal of many video systems is to quickly and efficiently decode compressed video information so as to provide motion video.
Generally motion video information is compressed, i.e., encoded, as a sequence of frames. Accordingly, to present the video information on a display screen, the compressed sequence of frames must be decompressed, i.e., decoded. One compression standard which has attained wide spread use for compressing and decompressing video information is the moving pictures expert group (MPEG) standard for video encoding and decoding.
Frames within the MPEG standard are divided into 16.times.16 pixel macroblocks. Each macroblock includes six 8.times.8 blocks: four luminance (Y) blocks, two chrominance (U and V) blocks. The luminance blocks correspond to sets of 16.times.16 pixels on a display and control the brightness of respective pixels. Each pair of U and V chrominance pixels to a large extent control the colors for sets of four pixels. For each set of four pixels on the display, there is a single U pixel characteristic and a single V pixel characteristic.
For example, referring to FIG. 1, labeled prior art, a frame presented by a typical display includes 240 lines of video information in which each line has 352 pixels. Accordingly, a frame includes 240.times.352=84,480 pixel locations. Under the MPEG standard, this frame of video includes 44 by 30 luminance blocks or 1320 blocks of luminance video information. Additionally, because each macroblock of information also includes two corresponding chrominance blocks, each frame of video information also includes 330 Y blocks and 330 U blocks. Accordingly, each frame of video information requires 126,720 pixels=1,013,760 megabits of bit mapped storage space for presentation on a display.
There are three types of frames of video information which are defined by the MPEG standard, intra-frames (I frame), forward predicted frames (P frame) and bi-predicted frames (B frame).
An I frame is encoded as a single image having no reference to any past or future frame. Each block of an I frame is encoded independently. Accordingly, when decoding an I frame, no motion processing is necessary. However, for the reasons discussed below, it is necessary to store and access I frames for use in decoding other types of frames.
A P frame is encoded relative to a past reference frame. A reference frame is a P or I frame. The past reference frame is the closest preceding reference frame. Each macroblock in a P frame can be encoded either as an I macroblock or as a P macroblock. A P macroblock is stored as a translated 16.times.16 block of a past reference frame plus an error term. To specify the location of the P macroblock, a motion vector (i.e., an indication of the relative position of the translated block in the previous reference frame to its position in the current frame) is also encoded.
A B frame is encoded relative to the past reference fame and a future reference frame. The future reference frame is the closest succeeding reference frame and the past reference frame is the closest preceding reference frame. Accordingly, the encoding of a B frame is similar to that of an P frame with the exception that a B frame motion vector may refer to areas in the future reference frame. For macroblocks that use both past and future reference frames, the two 16.times.16 areas are averaged. When decoding a B frame the current B macroblock is obtained by using macroblocks from past and or future reference frames plus an error term. The macroblocks from past and future reference frames are offset by motion vectors.
Referring to FIG. 2, in a typical decoding function, a frame is stored sequentially within memory. More specifically, the Y blocks of the frame are stored together sequentially (i.e., the first row of the frame is stored together, and then the next row, and so on), followed by the U blocks, which are stored together sequentially, followed by the V blocks, which are stored together sequentially. Accordingly, video information is stored in memory to correspond to physical locations of pixels within the frame without regard to the relationship of pixels within the same 8.times.8 block of video information.
Typical microprocessors employ caches. A cache is a small, fast memory which stores copies of the most frequently used information which is stored within a main memory. A common cache memory structure is a set associative cache; the set associative cache is organized in a two dimensional array of data lines, i.e., in a number of "sets" of data lines. The data lines are typically 16 to 32 bytes long. A two-way set associative cache is a two dimensional array which includes two sets of data lines.
Each microprocessor implements a cache fill method which attempts to fill the cache with data which is likely to be required by a program in the near future. A typical method is to fill an entire cache line when a memory location which is not already stored in the cache is accessed. The cache line is filled with the memory location being accessed plus additional nearby memory locations to fill the remaining portion of the cache line. This cache fill method is employed on most microprocessor since it is simple to implement.
Referring to FIG. 3, an example of cache addressing when a frame of video data is stored line by line in a main memory, but the data is decompressed block by block is shown. The data being decompressed is stored within the cache. More specifically, when the first pixel of chrominance block M is accessed (assuming it is not already present within the cache), 32 bytes of data are written into the cache. At most, only 8 bytes of the 32 bytes are associated with chrominance block M and the rest of the bytes are associated with chrominance blocks M+1, M+2 and so on. Pixel data in blocks M+1 and M+2 are typically not needed until after the processing of block M is completed and therefore, because of cache replacement techniques, this data is unlikely to still be in the cache when the data is needed. Also, when the second line of macroblock M is accessed, the pixel data is unlikely to be in the cache and a new cache line fill must occur. Likewise, when the first pixel of the luminance block is accessed (assuming that it is not already present within the cache), 32 bytes are written into the cache. At most, only 16 bytes of the 32 bytes are associated with the present luminance block, again resulting in inefficient cache performance.
While this cache storage structure results in inefficient cache performance, such a cache storage structure allows for relatively simple address computation when accessing the information which is stored within the memory. For example, Table 1 shows an example of software for generating addresses for accessing information which is stored within a picture oriented data structure. This example is set forth in the C programming language.
TABLE 1 ______________________________________ //***********The Picture-Oriented Structure(prior art)*********** struct Luminance.sub.-- Picture{ BYTE pixels[PICTURE.sub.-- SIZE]; //*Motion Compensation for Picture-Oriented Structure(prior art)* #define PICTURE.sub.-- WIDTH 352 void lum.sub.-- forw.sub.-- motion.sub.-- comp(int x, int y, struct Luminance.sub.-- picture*new.sub.-- lum.sub.-- pict, struct Luminance.sub.-- Picture*old.sub.-- lum.sub.-- pict, intx.sub.-- mv, int y.sub.-- mv) //Variables: // x,y - the starting point in the new picture // new.sub.-- lum.sub.-- pict - the data structure for the current frame // old.sub.-- lum.sub.-- pict - the data structure for the previous frame // x.sub.-- mv - the x component of the motion vector // y.sub.-- mv - the y component of the motion vector { BYTE *new.sub.-- pix, *old.sub.-- pix: int ptr, i, j: new.sub.-- pix = &(new.sub.-- lum.sub.-- pict-&gt;pixel[y*PICTURE.sub .-- WIDTH + (x+x.sub.-- mv)]); old.sub.-- pix = &(old.sub.-- lum.sub.-- pict-&gt;pixel(y+y.sub.-- mv) *PICTURE.sub.-- WIDTH+(x+x.sub.-- mv)]); ptr=0; for(i=0;i&lt;16;i++) { for(j=0;j&lt;16;j++) { new.sub.-- pix[ptr]=old.sub.-- pix[ptr]; ptr++; { ptr+=(PICTURE.sub.-- WIDTH-16); } ______________________________________
In operation, the software for generating addresses for accessing information which is stored within a picture oriented data structure first initializes the actual picture oriented data structure to provide a picture width of 352 pixels. Next, the local variables for the software are defined. Next, the places, i.e., the addresses, in each picture where data is moved to and from are generated. Next, a loop is entered for generating the addresses for accessing the information which is stored within the picture oriented data structure. Within this loop, the data for the first line of the block is accessed merely by incrementing the pointer from the address of the first pixel of the block. Additionally, the data for the first pixels of subsequent lines of the block are accessed by adding the picture width to the address of the first pixel of the previous line. Subsequent pixels in each line are accessed merely by incrementing the pointer from the address of the first pixel of the line.